#pragma once
#include <iostream>
#include <assert.h>

namespace lw
{

	template<class T>
	struct add_pointer { using type = T*; };
	template<class T>
	struct add_pointer<T*> { using type = T; };

	template<class T>
	using add_pointer_t = typename add_pointer<T>::type;

	template<class T>
	struct add_lvalue_reference { using type = T&; };
	template<class T>
	struct add_lvalue_reference<T&> { using type = T; };

	template<class T>
	using add_lvalue_reference_t = typename add_lvalue_reference<T>::type;

	template<class T>
	struct remove_const { using type = T; };
	template<class T>
	struct remove_const<const T> { using type = T; };

	template<class T>
	using remove_const_t = typename remove_const<T>::type;


	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		ListNode(const T& val = T())
			:_next(nullptr), _prev(nullptr), _data(val)
		{}
	};

	template<class T>
	struct __list_iterator
	{
		typedef __list_iterator<T> Self;
		typedef __list_iterator<remove_const_t<T>> Self_nor;
		typedef ListNode<remove_const_t<T>> ListNode;
		ListNode* _node;
		__list_iterator(ListNode* node)
			:_node(node)
		{}
		__list_iterator(const Self_nor& it)
			:_node(it._node)
		{}
		add_lvalue_reference_t<T> operator*()
		{
			return _node->_data;
		}
		add_pointer_t<T> operator->()
		{
			return &(_node->_data);
		}

		bool operator==(const Self_nor& s) const
		{
			return _node == s._node;
		}
		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

	};

	template<class T>
	class list
	{
		typedef ListNode<T> ListNode;
	public:
		typedef __list_iterator<T> iterator;
		typedef __list_iterator<const T> const_iterator;
		iterator begin() { return _node->_next; }
		iterator end() { return _node; }
		const_iterator begin() const { return _node->_next; }
		const_iterator end() const { return _node; }
		list()
		{
			init();
		}
		void init()
		{
			_node = new ListNode();
			_node->_prev = _node;
			_node->_next = _node;
		}
		iterator insert(iterator pos, const T& val)
		{
			ListNode* curr = pos._node;
			ListNode* prev = curr->_prev, * newnode = new ListNode(val);
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = curr;
			curr->_prev = newnode;

			return newnode;
		}

		iterator erase(iterator pos)
		{
			assert(pos != _node);

			ListNode* curr = pos._node;
			ListNode* prev = curr->_prev, * next = curr->_next;
			prev->_next = next;
			next->_prev = prev;

			delete curr;
			return next;
		}
		void push_back(const T& val)
		{
			insert(_node, val);
		}
		void push_front(const T& val)
		{
			insert(_node->_next, val);
		}
		void pop_back()
		{
			erase(_node->_prev);
		}
		void pop_front()
		{
			erase(_node->_next);
		}
	private:
		ListNode* _node = nullptr;
	};
}
